home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / cvrm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  11.8 KB  |  531 lines  |  [TEXT/R*ch]
  1. /*
  2.     module: cvrm.c
  3.     Purpose: miscellaneous cover manipulation
  4.     a) verify two covers are equal, check consistency of a cover
  5.     b) unravel a multiple-valued cover into minterms
  6.     c) sort covers
  7. */
  8.  
  9. #include "espresso.h"
  10.  
  11.  
  12. static void cb_unravel(c, start, end, startbase, B1)
  13. IN register pcube c;
  14. IN int start, end;
  15. IN pcube startbase;
  16. INOUT pcover B1;
  17. {
  18.     pcube base = cube.temp[0], p, last;
  19.     int expansion, place, skip, var, size, offset;
  20.     register int i, j, k, n;
  21.  
  22.     /* Determine how many cubes it will blow up into, and create a mask
  23.     for those parts that have only a single coordinate
  24.     */
  25.     expansion = 1;
  26.     (void) set_copy(base, startbase);
  27.     for(var = start; var <= end; var++) {
  28.     if ((size = set_dist(c, cube.var_mask[var])) < 2) {
  29.         (void) set_or(base, base, cube.var_mask[var]);
  30.     } else {
  31.         expansion *= size;
  32.     }
  33.     }
  34.     (void) set_and(base, c, base);
  35.  
  36.     /* Add the unravelled sets starting at the last element of B1 */
  37.     offset = B1->count;
  38.     B1->count += expansion;
  39.     foreach_remaining_set(B1, last, GETSET(B1, offset-1), p) {
  40.     INLINEset_copy(p, base);
  41.     }
  42.  
  43.     place = expansion;
  44.     for(var = start; var <= end; var++) {
  45.     if ((size = set_dist(c, cube.var_mask[var])) > 1) {
  46.         skip = place;
  47.         place = place / size;
  48.         n = 0;
  49.         for(i = cube.first_part[var]; i <= cube.last_part[var]; i++) {
  50.         if (is_in_set(c, i)) {
  51.             for(j = n; j < expansion; j += skip) {
  52.             for(k = 0; k < place; k++) {
  53.                 p = GETSET(B1, j+k+offset);
  54.                 (void) set_insert(p, i);
  55.             }
  56.             }
  57.             n += place;
  58.         }
  59.         }
  60.     }
  61.     }
  62. }
  63.  
  64.  
  65. pcover unravel_range(B, start, end)
  66. IN pcover B;
  67. IN int start, end;
  68. {
  69.     pcover B1;
  70.     int var, total_size, expansion, size;
  71.     register pcube p, last, startbase = cube.temp[1];
  72.  
  73.     /* Create the starting base for those variables not being unravelled */
  74.     (void) set_copy(startbase, cube.emptyset);
  75.     for(var = 0; var < start; var++)
  76.     (void) set_or(startbase, startbase, cube.var_mask[var]);
  77.     for(var = end+1; var < cube.num_vars; var++)
  78.     (void) set_or(startbase, startbase, cube.var_mask[var]);
  79.  
  80.     /* Determine how many cubes it will blow up into */
  81.     total_size = 0;
  82.     foreach_set(B, last, p) {
  83.     expansion = 1;
  84.     for(var = start; var <= end; var++)
  85.         if ((size = set_dist(p, cube.var_mask[var])) >= 2)
  86.         if ((expansion *= size) > 1000000)
  87.             fatal("unreasonable expansion in unravel");
  88.     total_size += expansion;
  89.     }
  90.  
  91.     /* We can now allocate a cover of exactly the correct size */
  92.     B1 = new_cover(total_size);
  93.     foreach_set(B, last, p) {
  94.     cb_unravel(p, start, end, startbase, B1);
  95.     }
  96.     free_cover(B);
  97.     return B1;
  98. }
  99.  
  100.  
  101. pcover unravel(B, start)
  102. IN pcover B;
  103. IN int start;
  104. {
  105.     return unravel_range(B, start, cube.num_vars-1);
  106. }
  107.  
  108. /* lex_sort -- sort cubes in a standard lexical fashion */
  109. pcover lex_sort(T)
  110. pcover T;
  111. {
  112.     pcover T1 = sf_unlist(sf_sort(T, lex_order), T->count, T->sf_size);
  113.     free_cover(T);
  114.     return T1;
  115. }
  116.  
  117.  
  118. /* size_sort -- sort cubes by their size */
  119. pcover size_sort(T)
  120. pcover T;
  121. {
  122.     pcover T1 = sf_unlist(sf_sort(T, descend), T->count, T->sf_size);
  123.     free_cover(T);
  124.     return T1;
  125. }
  126.  
  127.  
  128. /*  mini_sort -- sort cubes according to the heuristics of mini */
  129. pcover mini_sort(F, compare)
  130. pcover F;
  131. int (*compare)();
  132. {
  133.     register int *count, cnt, n = cube.size, i;
  134.     register pcube p, last;
  135.     pcover F_sorted;
  136.     pcube *F1;
  137.  
  138.     /* Perform a column sum over the set family */
  139.     count = sf_count(F);
  140.  
  141.     /* weight is "inner product of the cube and the column sums" */
  142.     foreach_set(F, last, p) {
  143.     cnt = 0;
  144.     for(i = 0; i < n; i++)
  145.         if (is_in_set(p, i))
  146.         cnt += count[i];
  147.     PUTSIZE(p, cnt);
  148.     }
  149.     FREE(count);
  150.  
  151.     /* use qsort to sort the array */
  152.     qsort((char *) (F1 = sf_list(F)), F->count, sizeof(pcube), compare);
  153.     F_sorted = sf_unlist(F1, F->count, F->sf_size);
  154.     free_cover(F);
  155.  
  156.     return F_sorted;
  157. }
  158.  
  159.  
  160. /* sort_reduce -- Espresso strategy for ordering the cubes before reduction */
  161. pcover sort_reduce(T)
  162. IN pcover T;
  163. {
  164.     register pcube p, last, largest = NULL;
  165.     register int bestsize = -1, size, n = cube.num_vars;
  166.     pcover T_sorted;
  167.     pcube *T1;
  168.  
  169.     if (T->count == 0)
  170.     return T;
  171.  
  172.     /* find largest cube */
  173.     foreach_set(T, last, p)
  174.     if ((size = set_ord(p)) > bestsize)
  175.         largest = p, bestsize = size;
  176.  
  177.     foreach_set(T, last, p)
  178.     PUTSIZE(p, ((n - cdist(largest,p)) << 7) + MIN(set_ord(p),127));
  179.  
  180.     qsort((char *) (T1 = sf_list(T)), T->count, sizeof(pcube), descend);
  181.     T_sorted = sf_unlist(T1, T->count, T->sf_size);
  182.     free_cover(T);
  183.  
  184.     return T_sorted;
  185. }
  186.  
  187. pcover random_order(F)
  188. register pcover F;
  189. {
  190.     pset temp;
  191.     register int i, k;
  192. #ifdef RANDOM
  193.     long random();
  194. #endif
  195.  
  196.     temp = set_new(F->sf_size);
  197.     for(i = F->count - 1; i > 0; i--) {
  198.     /* Choose a random number between 0 and i */
  199. #ifdef RANDOM
  200.     k = random() % i;
  201. #else
  202.     /* this is not meant to be really used; just provides an easy
  203.        "out" if random() and srandom() aren't around
  204.     */
  205.     k = (i*23 + 997) % i;
  206. #endif
  207.     /* swap sets i and k */
  208.     set_copy(temp, GETSET(F, k));
  209.     set_copy(GETSET(F, k), GETSET(F, i));
  210.     set_copy(GETSET(F, i), temp);
  211.     }
  212.     set_free(temp);
  213.     return F;
  214. }
  215.  
  216. /*
  217.  *  cubelist_partition -- take a cubelist T and see if it has any components;
  218.  *  if so, return cubelist's of the two partitions A and B; the return value
  219.  *  is the size of the partition; if not, A and B
  220.  *  are undefined and the return value is 0
  221.  */
  222. int cubelist_partition(T, A, B, comp_debug)
  223. pcube *T;            /* a list of cubes */
  224. pcube **A, **B;            /* cubelist of partition and remainder */
  225. unsigned int comp_debug;
  226. {
  227.     register pcube *T1, p, seed, cof;
  228.     pcube *A1, *B1;
  229.     bool change;
  230.     int count, numcube;
  231.  
  232.     numcube = CUBELISTSIZE(T);
  233.  
  234.     /* Mark all cubes -- covered cubes belong to the partition */
  235.     for(T1 = T+2; (p = *T1++) != NULL; ) {
  236.     RESET(p, COVERED);
  237.     }
  238.  
  239.     /*
  240.      *  Extract a partition from the cubelist T; start with the first cube as a
  241.      *  seed, and then pull in all cubes which share a variable with the seed;
  242.      *  iterate until no new cubes are brought into the partition.
  243.      */
  244.     seed = set_save(T[2]);
  245.     cof = T[0];
  246.     SET(T[2], COVERED);
  247.     count = 1;
  248.  
  249.     do {
  250.     change = FALSE;
  251.     for(T1 = T+2; (p = *T1++) != NULL; ) {
  252.         if (! TESTP(p, COVERED) && ccommon(p, seed, cof)) {
  253.         INLINEset_and(seed, seed, p);
  254.         SET(p, COVERED);
  255.         change = TRUE;
  256.         count++;
  257.         }
  258.     
  259.     }
  260.     } while (change);
  261.  
  262.     set_free(seed);
  263.  
  264.     if (comp_debug) {
  265.     printf("COMPONENT_REDUCTION: split into %d %d\n",
  266.         count, numcube - count);
  267.     }
  268.  
  269.     if (count != numcube) {
  270.     /* Allocate and setup the cubelist's for the two partitions */
  271.     *A = A1 = ALLOC(pcube, numcube+3);
  272.     *B = B1 = ALLOC(pcube, numcube+3);
  273.     (*A)[0] = set_save(T[0]);
  274.     (*B)[0] = set_save(T[0]);
  275.     A1 = *A + 2;
  276.     B1 = *B + 2;
  277.  
  278.     /* Loop over the cubes in T and distribute to A and B */
  279.     for(T1 = T+2; (p = *T1++) != NULL; ) {
  280.         if (TESTP(p, COVERED)) {
  281.         *A1++ = p;
  282.         } else {
  283.         *B1++ = p;
  284.         }
  285.     }
  286.  
  287.     /* Stuff needed at the end of the cubelist's */
  288.     *A1++ = NULL;
  289.     (*A)[1] = (pcube) A1;
  290.     *B1++ = NULL;
  291.     (*B)[1] = (pcube) B1;
  292.     }
  293.  
  294.     return numcube - count;
  295. }
  296.  
  297. /*
  298.  *  quick cofactor against a single output function
  299.  */
  300. pcover cof_output(T, i)
  301. pcover T;
  302. register int i;
  303. {
  304.     pcover T1;
  305.     register pcube p, last, pdest, mask;
  306.  
  307.     mask = cube.var_mask[cube.output];
  308.     T1 = new_cover(T->count);
  309.     foreach_set(T, last, p) {
  310.     if (is_in_set(p, i)) {
  311.         pdest = GETSET(T1, T1->count++);
  312.         INLINEset_or(pdest, p, mask);
  313.         RESET(pdest, PRIME);
  314.     }
  315.     }
  316.     return T1;
  317. }
  318.  
  319.  
  320. /*
  321.  *  quick intersection against a single output function
  322.  */
  323. pcover uncof_output(T, i)
  324. pcover T;
  325. int i;
  326. {
  327.     register pcube p, last, mask;
  328.  
  329.     if (T == NULL) {
  330.     return T;
  331.     }
  332.  
  333.     mask = cube.var_mask[cube.output];
  334.     foreach_set(T, last, p) {
  335.     INLINEset_diff(p, p, mask);
  336.     set_insert(p, i);
  337.     }
  338.     return T;
  339. }
  340.  
  341.  
  342. /*
  343.  *  A generic routine to perform an operation for each output function
  344.  *
  345.  *  func() is called with a PLA for each output function (with the output
  346.  *  part effectively removed).
  347.  *  func1() is called after reforming the equivalent output function
  348.  *
  349.  *  Each function returns TRUE if process is to continue
  350.  */
  351. foreach_output_function(PLA, func, func1)
  352. pPLA PLA;
  353. int (*func)();
  354. int (*func1)();
  355. {
  356.     pPLA PLA1;
  357.     int i;
  358.  
  359.     /* Loop for each output function */
  360.     for(i = 0; i < cube.part_size[cube.output]; i++) {
  361.  
  362.     /* cofactor on the output part */
  363.     PLA1 = new_PLA();
  364.     PLA1->F = cof_output(PLA->F, i + cube.first_part[cube.output]);
  365.     PLA1->R = cof_output(PLA->R, i + cube.first_part[cube.output]);
  366.     PLA1->D = cof_output(PLA->D, i + cube.first_part[cube.output]);
  367.  
  368.     /* Call a routine to do something with the cover */
  369.     if ((*func)(PLA1, i) == 0) {
  370.         free_PLA(PLA1);
  371.         return;
  372.     }
  373.  
  374.     /* intersect with the particular output part again */
  375.     PLA1->F = uncof_output(PLA1->F, i + cube.first_part[cube.output]);
  376.     PLA1->R = uncof_output(PLA1->R, i + cube.first_part[cube.output]);
  377.     PLA1->D = uncof_output(PLA1->D, i + cube.first_part[cube.output]);
  378.  
  379.     /* Call a routine to do something with the final result */
  380.     if ((*func1)(PLA1, i) == 0) {
  381.         free_PLA(PLA1);
  382.         return;
  383.     }
  384.  
  385.     /* Cleanup for next go-around */
  386.     free_PLA(PLA1);
  387.     
  388.  
  389.     }
  390. }
  391.  
  392. static pcover Fmin;
  393. static pcube phase;
  394.  
  395. /*
  396.  *  minimize each output function individually
  397.  */
  398. void so_espresso(PLA, strategy)
  399. pPLA PLA;
  400. int strategy;
  401. {
  402.     Fmin = new_cover(PLA->F->count);
  403.     if (strategy == 0) {
  404.     foreach_output_function(PLA, so_do_espresso, so_save);
  405.     } else {
  406.     foreach_output_function(PLA, so_do_exact, so_save);
  407.     }
  408.     sf_free(PLA->F);
  409.     PLA->F = Fmin;
  410. }
  411.  
  412.  
  413. /*
  414.  *  minimize each output function, choose function or complement based on the
  415.  *  one with the fewer number of terms
  416.  */
  417. void so_both_espresso(PLA, strategy)
  418. pPLA PLA;
  419. int strategy;
  420. {
  421.     phase = set_save(cube.fullset);
  422.     Fmin = new_cover(PLA->F->count);
  423.     if (strategy == 0) {
  424.     foreach_output_function(PLA, so_both_do_espresso, so_both_save);
  425.     } else {
  426.     foreach_output_function(PLA, so_both_do_exact, so_both_save);
  427.     }
  428.     sf_free(PLA->F);
  429.     PLA->F = Fmin;
  430.     PLA->phase = phase;
  431. }
  432.  
  433.  
  434. int so_do_espresso(PLA, i)
  435. pPLA PLA;
  436. int i;
  437. {
  438.     char word[32];
  439.  
  440.     /* minimize the single-output function (on-set) */
  441.     skip_make_sparse = 1;
  442.     (void) sprintf(word, "ESPRESSO-POS(%d)", i);
  443.     EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F);
  444.     return 1;
  445. }
  446.  
  447.  
  448. int so_do_exact(PLA, i)
  449. pPLA PLA;
  450. int i;
  451. {
  452.     char word[32];
  453.  
  454.     /* minimize the single-output function (on-set) */
  455.     skip_make_sparse = 1;
  456.     (void) sprintf(word, "EXACT-POS(%d)", i);
  457.     EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F);
  458.     return 1;
  459. }
  460.  
  461.  
  462. /*ARGSUSED*/
  463. int so_save(PLA, i)
  464. pPLA PLA;
  465. int i;
  466. {
  467.     Fmin = sf_append(Fmin, PLA->F);    /* disposes of PLA->F */
  468.     PLA->F = NULL;
  469.     return 1;
  470. }
  471.  
  472.  
  473. int so_both_do_espresso(PLA, i)
  474. pPLA PLA;
  475. int i;
  476. {
  477.     char word[32];
  478.  
  479.     /* minimize the single-output function (on-set) */
  480.     (void) sprintf(word, "ESPRESSO-POS(%d)", i);
  481.     skip_make_sparse = 1;
  482.     EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F);
  483.  
  484.     /* minimize the single-output function (off-set) */
  485.     (void) sprintf(word, "ESPRESSO-NEG(%d)", i);
  486.     skip_make_sparse = 1;
  487.     EXEC_S(PLA->R = espresso(PLA->R, PLA->D, PLA->F), word, PLA->R);
  488.  
  489.     return 1;
  490. }
  491.  
  492.  
  493. int so_both_do_exact(PLA, i)
  494. pPLA PLA;
  495. int i;
  496. {
  497.     char word[32];
  498.  
  499.     /* minimize the single-output function (on-set) */
  500.     (void) sprintf(word, "EXACT-POS(%d)", i);
  501.     skip_make_sparse = 1;
  502.     EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F);
  503.  
  504.     /* minimize the single-output function (off-set) */
  505.     (void) sprintf(word, "EXACT-NEG(%d)", i);
  506.     skip_make_sparse = 1;
  507.     EXEC_S(PLA->R = minimize_exact(PLA->R, PLA->D, PLA->F, 1), word, PLA->R);
  508.  
  509.     return 1;
  510. }
  511.  
  512.  
  513. int so_both_save(PLA, i)
  514. pPLA PLA;
  515. int i;
  516. {
  517.     if (PLA->F->count > PLA->R->count) {
  518.     sf_free(PLA->F);
  519.     PLA->F = PLA->R;
  520.     PLA->R = NULL;
  521.     i += cube.first_part[cube.output];
  522.     set_remove(phase, i);
  523.     } else {
  524.     sf_free(PLA->R);
  525.     PLA->R = NULL;
  526.     }
  527.     Fmin = sf_append(Fmin, PLA->F);
  528.     PLA->F = NULL;
  529.     return 1;
  530. }
  531.